//
//  MinPathSum.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/7/23.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  64. 最小路径和

import UIKit

/*
 64. 最小路径和
 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

 说明：每次只能向下或者向右移动一步。

 示例:

 输入:
 [
   [1,3,1],
   [1,5,1],
   [4,2,1]
 ]
 输出: 7
 解释: 因为路径 1→3→1→1→1 的总和最小。
 */

class MinPathSum: NSObject {
    /*
     该题是典型的动态规划题目
     
     给定矩阵 grid
     [1,3,1],
     [1,5,1],
     [4,2,1]
     
     由于只能从向下或者向右移动，那么要到达第一行或者第一列中某个格子就可以直接累加。
     我们同样创建一个m x n 的网格dp，
     [0,0,0],
     [0,0,0],
     [0,0,0]
     
     根据上述条件，可以先把到达第一行或者第一列中某个格子的总和写出来，即：
     [1,4,5],
     [2,0,0],
     [6,0,0]
     
     然后我们从1,1的位置开始算，由于只能从向下或者向右移动，那么坐标(i,j)的值就等于 min[dp(i-1,j),dp(i,j-1)) + grid(i,j)
     那么我们就可以推算到达每个格子的最小值
     [1,4,5],
     [2,7,6],
     [6,8,7]
     
     最后坐标(m-1,n-1)就是我们最后要得出的最小值
     
     
     
     大致思路如下：
     我们设f(i,j)表示到达坐标(i,j)的最小路径和。
     根据矩阵我们可以得知 第一行的格子只能从左边进入，第一列的格子只能从上边进入，起点(0,0)的最小是就是 grid(0,0)

     所以有：
     当 i = 0 ，j = 0时候，f(i,j) = grid(0,0)
     当 i = 0 ，j > 0时候，f(i,j) = dp(0,j-1) + grid(0,j)
     当 i > 0 ，j = 0时候，f(i,j) = dp(i-1,0) + grid(i,0)
     当 i > 0 ，j > 0时候，f(i,j) = min(dp(i-1,j),dp(i,j-1)) + grid(i,j)
     以上就是动态转移公式，我们就可以以此求解
     
     */
    
    func minPathSum(_ grid: [[Int]]) -> Int {
        if grid.count == 0 {
            return 0
        }
        
        let m = grid[0].count
        let n = grid.count
        
        var dp = [[Int]](repeating: [Int](repeating: 0, count: m), count: n)
        
        dp[0][0] = grid[0][0]
        
        for i in 0 ..< n {
            for j in 0 ..< m{
                if i == 0 && j == 0{
                    continue
                }else if i == 0 && j > 0 {
                    dp[i][j] = dp[0][j-1] + grid[0][j]
                }else if i > 0 && j == 0 {
                    dp[i][j] = dp[i-1][0] + grid[i][0]
                }else{
                    dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j]
                }
                
            }
        }
        
        return dp[n-1][m-1]
    }
}
